package bitOperation;

import java.util.Arrays;
import java.util.Comparator;

public class Test1 {
    public static void main(String[] args) {
        int[] arr = new int[]{1,0};
        System.out.println(Arrays.toString(bitOperationUtil.singleNumber3(arr)));
    }
}




class bitOperationUtil{

    /*260. 只出现一次的数字 III
     * 给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
     */
    public static int[] singleNumber3(int[] nums) {
        int a = 0, b= 0, res = 0, bitCount = 0;
        for(int num : nums){
            res ^= num;
            System.out.println(res + " ");
        }
        while(res != 0 && ((res >> bitCount) & 1) == 0)
            bitCount++;
        for(int num:nums)
            if((num >> bitCount & 1) == 1)
                a = a ^ num;
        b = a ^ res;
        return new int[]{a,b};
    }

    /*137. 只出现一次的数字 II
     * 给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
     */
    public static int singleNumber2(int[] nums) {
        int res = 0;
        // 测试案例有负数，考虑符号位
        for(int i=0; i< 32; i++){
            int count = 0; 
            for(int num : nums){
                if(((num >> i) & 1) == 1)
                    count++;
            }
            if(count % 3 != 0)
                res = res | (1 << i);
        }
        return res;
    }

    /*136. 只出现一次的数字
     * 给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
     */
    public static int singleNumber(int[] nums) {
        int res = 0;
        for(int num : nums)
            res ^= num;
        return res;
    }

    /*2917. 找出数组中的 K-or 值
     * 给你一个整数数组 nums 和一个整数 k 。让我们通过扩展标准的按位或来介绍 K-or 操作。
     * 在 K-or 操作中，如果在 nums 中，至少存在 k 个元素的第 i 位值为 1 ，那么 K-or 中的第 i 位的值是 1 。

    返回 nums 的 K-or 值。
     */
    public static int findKOr(int[] nums, int k) {
        int res=0;
        for(int i = 0; i < 31; i++){
            int count = 0;
            // 这种是破坏性的方法
            // 可以整体右移i位，不破坏原数组
            for(int j = 0; j < nums.length; j++){
                if((nums[j]&1) == 1)
                    count++;
                nums[j] >>>= 1;
            }
            res = count >= k ? res | (1 << i) : res;
        }
        return res;
    }

    /*191. 位1的个数 
     * 给定一个正整数 n，编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中 设置位(1)的个数（也被称为汉明重量）。
    */
    public static int hammingWeight(int n) {
        int count = 0;
        while(n > 0){
            if((n&1)==1)
                count++;
            n >>=1;
        }
        return count;
    }

    /*693. 交替位二进制数
     * 给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。
     */
    public static boolean hasAlternatingBits(int n) {
        int left=n>>1&1, right=n&1;
        while((n = (n >> 1)) > 0){
            if(right==left)
                return false;
            right=left;
            left=n>>1&1;
        }
        return true;
    }

    /*1342. 将数字变成 0 的操作次数 
     * 给你一个非负整数 num ，请你返回将它变成 0 所需要的步数。 
     * 如果当前数字是偶数，你需要把它除以 2 ；否则，减去 1 。
    */
    public static int numberOfSteps(int num) {
        int count = 0;
        while(num > 0){
            if((num&1) == 0)
                num >>= 1;
            else
                num -= 1;
            count++;
        }
        return count;
    }

    /* 3370 仅含置位位的最小整数
     * 给你一个正整数 n。
        返回 大于等于 n 且二进制表示仅包含 置位 位的 最小 整数 x 。
        置位 位指的是二进制表示中值为 1 的位。
     */
    public static int smallestNumber(int n){
        int res = 1;
        while(res < n){
            res = res << 1 | 1;
        }
        return res;
    }
    
    /*3226. 使两个整数相等的位更改次数
    给你两个正整数 n 和 k。
    你可以选择 n 的 二进制表示 中任意一个值为 1 的位，并将其改为 0。
    返回使得 n 等于 k 所需要的更改次数。如果无法实现，返回 -1。*/
    public static int minChanges(int n, int k) {
        int count = 0, mid = n ^ k;
        while(mid > 0){
            if((mid & 1) == 1)
                if((n&1) == 1)
                    count++;
                else
                    return -1;
            mid = mid >> 1;
            n = n >> 1;
        }
        return count;
    }

    /*1356. 根据数字二进制下 1 的数目排序
     * 给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。
        如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。
        请你返回排序后的数组。
     */
    public static int[] sortByBits(int[] arr) {
        Integer[] boxedArr = new Integer[arr.length];
        for(int i = 0; i < arr.length; i++){
            boxedArr[i] = arr[i];
        }
        // Arrays.sort只能对对象数组进行操作
        // 所以先提前转化成包装类
        Arrays.sort(boxedArr, new Comparator<Integer>(){
            @Override
            public int compare(Integer o1, Integer o2) {
                int count1 = Integer.bitCount(o1);
                int count2 = Integer.bitCount(o2);
                if(count1-count2==0){
                    return o1-o2;
                }
                return count1-count2;
            }
        });
        for(int i = 0; i < arr.length; i++){
            arr[i] = boxedArr[i];
        }
        return arr;
    }

    /*461. 汉明距离 
     * 两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
    给你两个整数 x 和 y，计算并返回它们之间的汉明距离。
    */
    public static int hammingDistance(int x, int y) {
        int res = x ^ y, count = 0;
        while(res > 0){
            if((res & 1) == 1)
                count++;
            res >>= 1;
        }
        return count;
    }
}